import java.util.HashMap;
import java.util.Map;
import java.util.*;
class Node2 {
    public int val;
    public Node2 prev;
    public Node2 next;
    public Node2 child;
};
class Node{
    public int key;
    public int val;
    public Node next;
    public Node prev;
    public Node(int key,int val){
        this.key=key;
        this.val=val;
    }
}
class DoubleLinkedList{
    public Node head;
    public Node tail;
    public DoubleLinkedList(){
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next=tail;
        tail.prev=head;
    }
    public void add(Node node){
        node.next=head.next;
        node.prev=head;
        head.next.prev=node;
        head.next=node;
    }
    public int delete(Node node){
        int key=node.key;
        node.next.prev=node.prev;
        node.prev.next=node.next;
        return key;
    }
    public int deleteLast(){
        if(head.next==tail){
            return -1;
        }
        return delete(tail.prev);
    }
}
class LRUCache {
    Map<Integer,Node> map;
    DoubleLinkedList doubleLinkedList;
    int size;
    public LRUCache(int capacity) {
        this.map=new HashMap<>();
        this.doubleLinkedList=new DoubleLinkedList();
        this.size=capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val=map.get(key).val;
        put(key,val);
        return val;
    }

    public void put(int key, int value) {
        Node node=new Node(key,value);
        if(map.containsKey(key)){
            doubleLinkedList.delete(map.get(key));
            doubleLinkedList.add(node);
            map.put(key,node);
        }else{
            if(size==map.size()){
                int tmp=doubleLinkedList.deleteLast();
                map.remove(tmp);
            }
            map.put(key,node);
            doubleLinkedList.add(node);
        }
    }
}














class Node1{
    public int val;
    public int key;
    public Node1 next;
    public Node1 prev;
    public Node1(int key,int val){
        this.val=val;
        this.key=key;
    }
}
class DoubleLinkedList1{
    public Node1 head;
    public Node1 tail;
    public DoubleLinkedList1(){
        head=new Node1(0,0);
        tail=new Node1(0,0);
        head.next=tail;
        tail.prev=head;
    }
    public void add(Node1 node){
        node.next=head.next;
        node.prev=head;
        head.next.prev=node;
        head.next=node;
    }
    public int delete(Node1 node){
        int key=node.key;
        node.next.prev=node.prev;
        node.prev.next=node.next;
        return key;
    }
    public int deleteLast(){
        if(head.next==tail){
            return -1;
        }
        return delete(tail.prev);
    }

}
class LRUCache1 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int len=nums.length;
        Arrays.sort(nums);
        for(int i=0;i<len;i++){
            if(nums[i]<0&&k>0){
                k--;
                nums[i]=-nums[i];
            }
        }
        Arrays.sort(nums);
        if((k&1)==1){
            nums[0]*=-1;
        }
        int sum=0;
        for(int num : nums){
            sum+=num;
        }
        return sum;
    }
    public HashMap<Integer,Node1> map;
    public DoubleLinkedList1 doubleLinkedList;
    int size;
    public LRUCache1(int capacity) {
        this.map=new HashMap<>();
        this.doubleLinkedList=new DoubleLinkedList1();
        this.size=capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        int val=map.get(key).val;
        put(key,val);
        return val;
    }

    public void put(int key, int value) {
        Node1 node=new Node1(key,value);
        if(map.containsKey(key)){
            doubleLinkedList.delete(map.get(key));
            doubleLinkedList.add(node);
            map.put(key,node);
        }else{
            if(size==map.size()){
                int k=doubleLinkedList.deleteLast();
                map.remove(k);
            }
            doubleLinkedList.add(node);
            map.put(key,node);
        }
    }
}















public class projct {
    public Node2 flatten(Node2 head) {
        dfs(head);
        return head;
    }
    public Node2 dfs(Node2 head){
        Node2 prev=null;
        Node2 cur=head;
        while (cur!=null){
            Node2 next=cur.next;
            if(cur.child!=null){
                Node2 newhead=dfs(cur.child);
                next=cur.next;
                cur.child.prev=cur;
                cur.next=cur.child;
                if(next!=null){
                    next.prev=newhead;
                    newhead.next=next;
                }
                cur.child=null;
                prev=newhead;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        return prev;
    }
}
